<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>二叉搜索树封装</title>
</head>

<body>
  <script>
    // 封装二叉搜索树类
    function BinarySerachTree() {
      // 节点类
      function Node(key) {
        this.key = key
        this.left = null
        this.right = null
      }
      // 属性
      this.root = null

      // 方法
      // 插入数据:对外给用户调用的方法
      BinarySerachTree.prototype.insert = function (key) {
        // 1.根据key创建节点
        const newNode = new Node(key)
        // 2.判断根节点是否有值
        if (this.root == null) {
          this.root = newNode
        } else {
          this.insertNode(this.root, newNode)
        }
      }
      BinarySerachTree.prototype.insertNode = function (node, newNode) {
        if (newNode.key < node.key) { // 向左查找
          if (node.left == null) {
            node.left = newNode
          } else {
            this.insertNode(node.left, newNode)
          }
        } else { // 向右查找
          if (node.right == null) {
            node.right = newNode
          } else {
            this.insertNode(node.right, newNode)
          }
        }
      }
      // 树的遍历
      // 1.先序遍历
      BinarySerachTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTraversalNode(this.root, handler)
      }
      BinarySerachTree.prototype.preOrderTraversalNode = function (node, handler) {
        if (node != null) {
          // 1.处理经过的节点
          handler(node.key)
          // 2.处理经过节点的左子节点
          this.preOrderTraversalNode(node.left, handler)
          // 2.处理经过节点的右子节点
          this.preOrderTraversalNode(node.right, handler)
        }
      }

    }
    let test = new BinarySerachTree()
    // 插入数据
    test.insert(10)
    test.insert(12)
    test.insert(7)
    test.insert(6)
    test.insert(15)
    // 测试遍历
    let resultString = ''
    test.preOrderTraversal(function (key) {
      resultString += key + " "
    })
    alert(resultString)
  </script>
</body>

</html>